import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

//最长等差数列
//测试链接：https://leetcode.cn/problems/longest-arithmetic-subsequence/
public class LongestArithSeqLength {
    public int longestArithSeqLength(int[] nums) {
        // 优化
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(nums[0], 0);

        // 建表
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) // 初始化
            Arrays.fill(dp[i], 2);

        int ret = 2;
        for (int i = 1; i < n; i++) // 固定倒数第⼆个数
        {
            for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数
            {
                int a = 2 * nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return ret;
    }
}
